`
https://leetcode.cn/problems/sort-list
`

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var sortList = function (head) {
  // 处理边界情况
  if (!head || !head.next) return head;

  // 计算链表长度
  let length = 0;
  let curr = head;
  while (curr) {
    length++;
    curr = curr.next;
  }

  const dummy = new ListNode(0);
  dummy.next = head;

  // 自底向上的归并排序
  for (let size = 1; size < length; size = size * 2) {
    let prev = dummy;
    curr = dummy.next;

    while (curr) {
      // 获取并切分第一个子链表
      let left = curr;
      for (let i = 1; i < size && curr.next; i++) {
        curr = curr.next;
      }
      let right = curr.next;
      curr.next = null; // 断开第一个子链表

      // 获取并切分第二个子链表
      curr = right;
      for (let i = 1; i < size && curr && curr.next; i++) {
        curr = curr.next;
      }

      // 保存下一组待处理的链表
      let next = null;
      if (curr) {
        next = curr.next;
        curr.next = null; // 断开第二个子链表
      }

      // 合并两个子链表
      let { head: mergedHead, tail: mergedTail } = merge(left, right);
      prev.next = mergedHead;
      prev = mergedTail;

      // 继续处理下一组
      curr = next;
    }
  }

  return dummy.next;
};

// 合并两个有序链表，返回合并后的头节点和尾节点
function merge(left, right) {
  const dummy = new ListNode(0);
  let tail = dummy;

  while (left && right) {
    if (left.val <= right.val) {
      tail.next = left;
      left = left.next;
    } else {
      tail.next = right;
      right = right.next;
    }
    tail = tail.next;
  }

  // 连接剩余的链表部分
  tail.next = left || right;

  // 找到合并后链表的尾节点
  while (tail.next) {
    tail = tail.next;
  }

  return { head: dummy.next, tail: tail };
}